public class Solution {
    public static int maxProfit(int k, int[] prices) {
        int n = prices.length;
        int[][] f = new int[k][n];
        int[][] g = new int[k][n];
        int INF = -0x3f3f3f3f;
        for(int i = 1;i < k;i++) {
            f[i][0] = INF;
            g[i][0] = INF;
        }
        f[0][0] = -prices[0];
        for (int i = 0; i < k; i++) {
            for (int j = 1; j < n; j++) {
                f[i][j] = Math.max(f[i][j - 1], g[i][j - 1] - prices[j]);
                g[i][j] = g[i][j - 1];
                if (i - 1 >= 0)
                    g[i][j] = Math.max(f[i - 1][j-1] + prices[j], g[i][j]);


            }
        }
        int max = 0;
        for(int i = 0;i < k;i++) max = Math.max(max,g[i][n]);
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {3,2,6,5,0,3};
        maxProfit(2,arr);
    }

}
